Міністерство освіти і науки України
Національний університет “Львівська політехніка”
Кафедра Програмного забезпечення
Курсова робота
з дисципліни “ Методи та засоби комп’ютерних інформаційних технологій ”
на тему « Арифметичне кодування-декодування »
Львів 2007
АНОТАЦІЯ
В даній курсовій роботі розглянуто один із алгоритмів стиснення інформації, а саме алгоритм «Арифметичне кодування-декодування». Реалізовано програму, яка виконує його дії і показано її основні функції. Приведений огляд інших алгоритмів стиснення інформації і їх порівняння з даним.
ЗМІСТ
Вступ
1. Огляд методів стискання інформації
1.1 Загальні характеристики методів стискання інформації
1.2 Кодування Хаффмена
1.3 Дворівневе кодування. Алгоритм Лемпеля-Зіва
1.4 Сімейство алгоритмів LZ78 (LZW, MW, AP, Y)
1.5 Алгоритм арифметичного кодування
2. Формулювання поставленої задачі
Постановка задачі
Функціональні вимоги
3. Реалізація алгоритму арифметичного кодування - декодування
Загальний опис алгоритму арифметичного кодування – декодування
3.1.1 Фіксована модель
3.1.2 Адаптивна модель
3.1.3 Проблеми переповнення і завершення кодування
Реалізація арифметичного кодування
Попередній аналіз файлу
Кодування файлу
Додаткова обробка закодованого файлу
Реалізація арифметичного декодування
Додаткова обробка закодованого файлу
Декодування файлу
Збереження таблиці
Проектування інтерфейсу користувача
Ефективність стискання арифметичного кодування
Інструкція по використанню розробленої програми
Висновок
Список літератури
ВСТУП
Проблема стискання та кодування інформації з’явилась набагато раніше ніж, власне, термін “інформація”. Згадаємо, що принаймні за часів Римсокої імперії армія використовувала метод шифрування повідомлень з метою її захисту від ворогів. Так званий шифр Цезаря став першим з відомих на сьогодні методів шифрування з таємним ключом. Іншим прикладом кодування є писемність, яка виникла так давно, що точних даних про конкретний час її появи не існує і, мабуть, ніколи не буде знайдено.
В другій половині ХХ-го століття з винайденням та розвитком ЕОМ проблема стискання та кодування привернула до себе увагу, бо з чисто теоретичної перетворилася в прикладну та вкрай необхідну. Стрімко зросли обсяги даних, з’явилась потреба в передачі дискретної інформації на далекі відстані з достатньою надійністю, проблема захисту такої інформації від несанкціонованого доступу і т. д. З розвитком комп’ютерних мереж (зокрема, INTERNET) обсяг інформації, що передається, швидко зростає і вимагає її мінімізації шляхом специфічного кодування для підтримання швидкодії мережі. Можна навести багато інших застосувань кодування інформації.
Арифметичне кодування є одним з перспективних методів стиску інформації, та, в деякому розумінні, її шифрування. Це кодування дозволяє пакувати символи вхідного алфавіту за умови, що розподіл частот цих символів відомий. Концепція методу була розроблена Еліасом в 60-х роках. Після цього метод був суттєво розвинутий та вдосконалений. Арифметичне кодування є оптимальним, досягає теоретичної границі ступеня стиску, - ентропії вхідного потоку.
1. Огляд методів стискання інформації
1.1. Загальні характеристики методів стискання інформації
Методи стискання інформації мають досить довгу історію. Найбільш відомий – це кодування довжин серій (run length encoding, RLE). Зміст методу – заміна ланцюжків символів, що повторюються, на один цей символ та лічильник повторювання. Проблема полягає в тому, щоб декодер міг відрізнити у вихідному потоці таку кодовану серію від інших символів. Розв’язок цієї проблеми очевидний – додавати до таких ланцюжків деякі заголовки (наприклад, використовувати перший біт як ознаку кодованої серії). Метод є досить ефективним для графічних зображень у форматі “байт на піксел” (наприклад, формат PCX використовує кодування RLE).
Недоліки методу RLE є очевидними: це, передусім, низька пристосованість до багатьох розповсюджених типів файлів, наприклад, тек...
